package Top101K;

/**
 * @Author quan
 * @Description 判断链表中是否有环
 * @Date 2023/12/6 11:38
 */
public class BM6_hasCycle {
    /**
     * 使用快慢指针解决，快指针每次走两步，慢指针每次走一步，如果存在环，则快指针一定在某一个时刻追上慢指针。如果快指针为null时还没追上，则一定没有环
     * @param head
     * @return
     */
    public boolean hasCycle(ListNode head) {
        // 边界条件
        if(head == null){
            return false;
        }
        // 1-定义两个指针
        ListNode fast = head;
        ListNode low = head;
        // 2-结束条件：快指针遍历结束的时候还没追上慢指针说明没有环
        while (fast.next != null && fast.next.next != null){
            fast = fast.next.next;
            low = low.next;
            if(fast.val == low.val){
                return true;
            }
        }
        return false;
    }
}
